package com.company.algo.listnode;

import com.company.algo.pojo.ListNode;

public class CircleNodes {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        do{
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        }while (slow!=fast);
        fast = head;
        while (fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    //457. 环形数组是否存在循环
    public boolean circularArrayLoop(int[] nums){
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i;
            int fast = nxt(i,nums);
            //快慢指针，符号相同保证是同一个方向移动
            while (nums[slow]*nums[fast] > 0 && nums[fast]*nums[nxt(fast,nums)] > 0){
                if (slow == fast){
                    if (slow == nxt(slow,nums)) break;  //环的长度必须大于1
                    else return true;
                }
                slow = nxt(slow,nums);
                fast = nxt(nxt(fast,nums),nums);
            }
            //访问过的置为0
            /*如果上面那轮没有return，说明上面遍历过的元素都不可能成环，为避免再次遍历陷入无效查找，
            故将查找过的元素置零，再次遍历时直接跳过*/
            while (nums[i]*nums[nxt(i,nums)]>0){
                int tmp = nxt(i,nums);
                nums[i] = 0;
                i = tmp;
            }
        }
        return false;
    }
    public int nxt(int i,int[] nums){
        int n = nums.length;
        return  ((i+nums[i]) % n + n)%n ;
    }

    public static void main(String[] args) {
        CircleNodes Main = new CircleNodes();
        int[] nums = {2,-1,1,1,2};
        System.out.println(Main.circularArrayLoop(nums));

    }
}
